// 《围棋》作者版权所有。保留所有权利。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package mvs

import (
	"fmt"

	"golang.org/x/mod/module"
)

// Graph实现了MVS算法的增量版本，
// 需求由调用者推送，而不是由MVS遍历拉动。
type Graph struct {
	cmp   func(v1, v2 string) int
	roots []module.Version

	required map[module.Version][]module.Version

	isRoot   map[module.Version]bool // 对于根包含true，对于可到达的非根包含false 
	selected map[string]string       // 路径→ version 
}

// NewGraph返回一个增量MVS图，该图只包含一组根
// 依赖项，并使用给定的max函数表示版本字符串。
// 
// 调用方必须确保在图形
// 可能正在使用时，根切片未被修改。
func NewGraph(cmp func(v1, v2 string) int, roots []module.Version) *Graph {
	g := &Graph{
		cmp:      cmp,
		roots:    roots[:len(roots):len(roots)],
		required: make(map[module.Version][]module.Version),
		isRoot:   make(map[module.Version]bool),
		selected: make(map[string]string),
	}

	for _, m := range roots {
		g.isRoot[m] = true
		if g.cmp(g.Selected(m.Path), m.Version) < 0 {
			g.selected[m.Path] = m.Version
		}
	}

	return g
}

// Require添加了模块m需要reqs中所有模块的信息。
// reqs切片在传递到Require后不得修改。
// 
// m必须可以通过g的目标、
// 的一些现有需求链访问，并且必须尚未调用Require。
// 
// 如果reqs中的任何模块与g的目标模块具有相同的路径，
// 目标模块的优先级必须高于req中的版本。
func (g *Graph) Require(m module.Version, reqs []module.Version) {
	// 为了帮助捕获断开连接的图形错误，强制要求所有必需的版本
	// 实际上都可以从根目录访问（因此应该影响
	// 它们命名的模块的选定版本）。
	if _, reachable := g.isRoot[m]; !reachable {
		panic(fmt.Sprintf("%v is not reachable from any root", m))
	}

	// 将请求截断到其容量，以避免在以后返回时出现别名错误
	// 从RequiredBy返回并附加到。
	reqs = reqs[:len(reqs):len(reqs)]

	if _, dup := g.required[m]; dup {
		panic(fmt.Sprintf("requirements of %v have already been set", m))
	}
	g.required[m] = reqs

	for _, dep := range reqs {
		// 无论是否选中，标记dep可访问。
		if _, ok := g.isRoot[dep]; !ok {
			g.isRoot[dep] = false
		}

		if g.cmp(g.Selected(dep.Path), dep.Version) < 0 {
			g.selected[dep.Path] = dep.Version
		}
	}
}

// RequiredBy返回传递给Require for m（如果有）的需求片段，
// ，其容量减少到其长度。
// 如果m没有调用Require，RequiredBy（m）返回ok=false。
// 
// 调用者不能修改返回的切片，但可以安全地附加到它
// 并且可以依赖它不被修改。
func (g *Graph) RequiredBy(m module.Version) (reqs []module.Version, ok bool) {
	reqs, ok = g.required[m]
	return reqs, ok
}

// Selected返回给定模块路径的所选版本。
// 
// 如果未选择版本，则所选版本返回“无”。
func (g *Graph) Selected(path string) (version string) {
	v, ok := g.selected[path]
	if !ok {
		return "none"
	}
	return v
}

// BuildList返回图中所有模块的选定版本，
// 从g根中每个模块路径的选定版本开始。
// 
// 列表中其余元素的顺序是确定性的
// 但是任意的。
func (g *Graph) BuildList() []module.Version {
	seenRoot := make(map[string]bool, len(g.roots))

	var list []module.Version
	for _, r := range g.roots {
		if seenRoot[r.Path] {
			// 同一根的多个副本，具有相同或不同的版本，
			// 有点退化：我们将考虑两个根的传递性
			// 要求，但可能只能选择较高的一个。然而——特别是考虑到我们需要
			// 请稍后查看根映射——支持这个
			// 退化案例比禁止它更简单。
			continue
		}

		if v := g.Selected(r.Path); v != "none" {
			list = append(list, module.Version{Path: r.Path, Version: v})
		}
		seenRoot[r.Path] = true
	}
	uniqueRoots := list

	for path, version := range g.selected {
		if !seenRoot[path] {
			list = append(list, module.Version{Path: path, Version: version})
		}
	}
	module.Sort(list[len(uniqueRoots):])

	return list
}

// WalkBreadthFirst以宽度优先的顺序为每个模块调用f一次
// 版本，而不是图中显示的“无”，无论是否选择了该版本。
func (g *Graph) WalkBreadthFirst(f func(m module.Version)) {
	var queue []module.Version
	enqueued := make(map[module.Version]bool)
	for _, m := range g.roots {
		if m.Version != "none" {
			queue = append(queue, m)
			enqueued[m] = true
		}
	}

	for len(queue) > 0 {
		m := queue[0]
		queue = queue[1:]

		f(m)

		reqs, _ := g.RequiredBy(m)
		for _, r := range reqs {
			if !enqueued[r] && r.Version != "none" {
				queue = append(queue, r)
				enqueued[r] = true
			}
		}
	}
}

// FindPath报告一条最短的需求路径，该路径从
// 图形的一个根开始，到f（m）返回true的模块版本m结束，或者如果不存在这样的路径，则报告
// nil。
func (g *Graph) FindPath(f func(module.Version) bool) []module.Version {
	// firstRequires[a]=b意味着在
	// 需求图的广度优先遍历中，模块版本a是b首先需要的。
	firstRequires := make(map[module.Version]module.Version)

	queue := g.roots
	for _, m := range g.roots {
		firstRequires[m] = module.Version{}
	}

	for len(queue) > 0 {
		m := queue[0]
		queue = queue[1:]

		if f(m) {
			// 构造反向路径（因为我们从远的
			// 端点开始），然后反向。
			path := []module.Version{m}
			for {
				m = firstRequires[m]
				if m.Path == "" {
					break
				}
				path = append(path, m)
			}

			i, j := 0, len(path)-1
			for i < j {
				path[i], path[j] = path[j], path[i]
				i++
				j--
			}

			return path
		}

		reqs, _ := g.RequiredBy(m)
		for _, r := range reqs {
			if _, seen := firstRequires[r]; !seen {
				queue = append(queue, r)
				firstRequires[r] = m
			}
		}
	}

	return nil
}
